The LDPC (Low-Density Parity-Check) code is an error correction code applied in encoding/decoding of message transmissions in noisy channels of communication. An LDPC code C is defined by a sparse parity-check matrix (abbreviated as PCM thereafter) H. The “low-density” in LDPC is attributed to that the density of “1s (ones)” in the PCM H corresponding to an LDPC code is low. This characteristic of “low density” enables the low complexity of decoding operations. The LDPC code has a superior error correction efficacy and is thus widely used in channel encoding techniques in the next generation of communication systems, for example, WiMAX (Worldwide Interoperability for Microwave Access).
The WiMAX standard adopts QC-LDPC (quasi-cyclic LDPC) codes, which are block-type error correction codes. When defining a QC-LDPC code C, it usually requires the definition of a PCM H corresponding to the QC-LDPC code. H can be represented as an M×N (M by N) matrix, which can be expanded from an Mb×Nb binary base matrix Hb, wherein M=z×Mb and N=z×Nb, and z is a positive integer called the expansion factor. In matrix Hb, each “0 (zero)” can be replaced by a z×z zero matrix, and each “1 (one)” can be replaced by a z×z permutation matrix. The z×z permutation matrix is obtained via cyclically right shifting an identity matrix. FIG. 1 shows the presentation of a parity-check matrix H, wherein Pij can be a z×z permutation matrix or a z×z zero matrix, and wherein i and j of matrix Hb are respectively the row index and the column index.
As each permutation matrix is obtained via cyclically right shifting an identity matrix, a binary base matrix and the shift indices of the permutation matrices can be integrated to form a concise prototype matrix Hbm. The prototype matrix Hbm has the same dimension as the binary base matrix Hb does. Each “0 (zero)” of the binary base matrix Hb is replaced by a blank or a negative value, such as “−1”, representing a zero matrix completely formed of zeros, and each “1 (one)” of the binary base matrix Hb is replaced by the displacement value of the cyclic right shifts. The prototype matrix Hbm can be directly expanded to obtain a parity-check matrix H. FIG. 2A and FIG. 2B respectively show examples of a prototype matrix Hbm and a parity-check matrix H. In FIG. 2B, 03×3 expresses a 3×3 zero matrix.
The WiMAX standard includes six types of code rates or classes: 1/2, 2/3A, 2/3B, 3/4A, 3/4B and 5/6, and respectively provide one prototype matrix for each of the code class. Therefore, there are totally six different prototype matrices in the WiMAX standard. FIG. 3 shows the prototype matrix Hbm with the expansion factor z being 96 and the code rate being 5/6. In the WiMAX standard, each class includes 19 different QC-LDPC codes with different code lengths respectively. The code lengths are respectively determined by 19 different expansion factors z, including 24, 28, 32, . . . , and 96. The code length can be represented by 24z. Accordingly, the WiMAX totally has 114 (=6×19) types of QC-LDPC codes.
In the WiMAX standard, each prototype matrix is assigned by the code rate. In other words, an LDPC code is assigned by parameters of the code rate and the code length. Therefore, it is an important subject to simplify the hardware implementation via designing a flexible hardware architecture, whereby most of the hardware resources can be re-used in different WiMAX modes.
An LDPC code is usually graphically expressed by a Tanner graph. The Tanner graph is a bipartite graph. FIG. 4A and FIG. 4B respectively show an LDPC code and the Tanner graph corresponding to the LDPC code. Each row of a PCM H is corresponding to a check node, and each column thereof is corresponding to a variable node. The PCM H in FIG. 4A has six rows and nine columns. Thus, the corresponding Tanner graph has nine variable nodes in the top layer and six check nodes in the bottom layer, wherein the numbers in the circles and squares respectively represent the column indices and the row indices. When an element (i, j) in the PCM H is 1, there is an edge connecting the ith check node and the jth variable node.
The error correction efficiency of the LDPC code positively correlates with the number of iterations. A noisier channel thus requires a greater number of iterations to improve the BER (Bit Error Rate) performance. For increasing the throughput of a partially-parallel decoder, it is necessary to decrease the number of the processing cycles of a single iteration or the number of iterations to achieve a given BER. A conventional overlapped decoding technology can reduce the number of the processing cycles via scheduling the operations of the check nodes and variable nodes to concurrently undertake some operations of them. Further, in a conventional TPMP (Two Phase Message Passing) decoding technology, the variable nodes can only use the C2V (check to variable) messages generated in the preceding iteration to undertake the updates. Thus, a greater number of iterations is required to obtain a given BER performance.